﻿// Layout POJ - 3169.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3169

/*
和其他人一样，奶牛在排队领取饲料时也喜欢站在朋友身边。FJ 有 N 头（2 <= N <= 1,000 头）编号为 1...N 的奶牛站在一条直线上等待喂食。
这些奶牛按照编号的顺序排列，由于它们很爱出风头，有可能两头或更多的奶牛排在完全相同的位置上
（也就是说，如果我们把每头奶牛看作位于数线上的某个坐标上，那么两头或更多的奶牛就有可能共享同一个坐标）。

有些奶牛喜欢对方，希望彼此排在一定距离之内。有些牛非常不喜欢对方，希望至少相隔一定距离。
一个 ML（1 <= ML <= 10,000）约束列表描述了哪些奶牛喜欢对方，以及它们可以分开的最大距离；
随后的一个 MD 约束列表（1 <= MD <= 10,000）告诉我们哪些奶牛不喜欢对方，以及它们必须分开的最小距离。

您的任务是尽可能计算出奶牛 1 和奶牛 N 之间满足距离约束的最大可能距离。
输入
第 1 行 三个空格分隔的整数： N、ML 和 MD。

第 2...ML+1 行：每行包含三个空格分隔的正整数： 牛 A 和牛 B 最多相距 D（1 <= D <= 1,000,000）。

行 ML+2...ML+MD+1：每行包含三个空格分隔的正整数： 奶牛 A 和 B 必须至少相距 D（1 <= D <= 1,000,000）。
输出
第 1 行： 一个整数。如果不可能排成一行，则输出-1。 如果奶牛 1 和 N 可以任意分开，则输出-2。
否则，输出奶牛 1 和 N 之间的最大可能距离。

样本

4 2 1
1 3 10
2 4 20
2 3 3

27
提示
样本解释：
有 4 头奶牛。1 号牛和 3 号牛之间的距离不得超过 10 个单位，2 号牛和 4 号牛之间的距离不得超过 20 个单位，
2 号牛和 3 号牛互不相像，它们之间的距离不得少于 3 个单位。
根据数线上的坐标，最好的布局是将 1 号牛放在 0 处，2 号牛放在 7 处，3 号牛放在 10 处，4 号牛放在 27 处。
*/




int main()
{



	return 0;
}

